'''
Created on December 9, 2009
# Problem Set 3 (Part IV)
# Name: Noah Spahn
# Collaborators: none
# Time: 1:25
'''
from string import *

def subStringMatchExact(target,key):
    """
    Returns a tuple of indexes for matching instances of key in the provided target

    """
    start = 0
    position = 0
    tuple = ()
    if len(key)==0:return None
    while position != -1:
        position = find(target,key,start)
        if position >= 0:    tuple = tuple + (position,)
        start = position + len(key)
    return tuple

def constrainedMatchPair(firstMatch,secondMatch,length):
    """ Given indexes of string matches (n and k) for a key broken into two parts (with one character missing) 
    and the length of the key, return a tuple of the correct matches, where n+m+1==k"""
    start = 0
    position = 0
    tuple = ()
    if secondMatch and firstMatch != None: # Rough Error checking
        for n in firstMatch:
            for k in secondMatch:
                if n+length+1==k:
                    tuple=tuple+(n,)
    elif firstMatch == None: # we are dealing with the case of *234, where first char is a variable
        for k in secondMatch:
            if k !=0: tuple = tuple+(k-1,)
    elif secondMatch == None: # we are dealing with the case of 123*, where last char is a variable
        for n in firstMatch:
            tuple = tuple+(n,)
    return tuple

### the following procedure you will use in Problem 3
def subStringMatchOneSub(target,key):
    """
    Returns a tuple of indexes for matching instances of key in the provided target
    Search for all locations of key in target, with one substitution
    target: string
    key: sub string
    """
    allAnswers = ()
    for miss in range(0,len(key)):
        key1 = key[:miss]
        key2 = key[miss+1:]
        
        match1 = subStringMatchExact(target,key1)
        match2 = subStringMatchExact(target,key2)

        filtered = constrainedMatchPair(match1,match2,len(key1))
        allAnswers = allAnswers + filtered
    return allAnswers

def subStringMatchExactlyOneSub(target,key):
    """
    Returns a tuple of indexes for matching instances of key in the provided target
    Search for all locations of key in target, with one substitution
    target: string
    key: sub string
    """    
    tuple = ()
    t1 = subStringMatchExact(target,key)
    print "t1:::",t1
    t2 = subStringMatchOneSub(target,key)
    print "t2:::",t2
    for sub in t2:
        if sub not in t1:
            tuple = tuple +(sub,)
        else:print "sub:",sub
    return tuple

# References
# very helpful!!! http://diveintopython.org/getting_to_know_python/tuples.html